【阅读时间】10000+字 | 17 - 22 min
【阅读内容】Google面试题：100层楼，两个鸡蛋最少用多少次能测出鸡蛋的会在哪一层碎

1. 题目描述

有栋楼高100层，一个鸡蛋从第x层以上($>$)的楼层落下来会摔碎，在第x层和以下($\leqslant$)的楼层落下不会摔碎。给你2个鸡蛋，设计方案找出x，保证在最坏情况下， 最小扔鸡蛋尝试的次数

有时候仍的东西会变，比如瓶子

这道题目的整个解答过程涉及给类逻辑思维，工程思维，当真是一道海纳百川的面试题，也难怪Goolge会以这道题做了多年的试金石

1.1 求什么？

利用抽象思维，符号化题目描述

⭐️〔题目要求〕找到 $x$ 层落下不会碎，$x+1$ 层落下会碎的临界层所需要的最少尝试次数 $r$ (r for result)

2. 解题思路

使用等价思维，如何计算出最小的尝试次数？使用函数方法表示为：如何计算出这个结果，找出公式 $r = f()$

2.1 一个鸡蛋

假设最后结果设为 $r$ 次（r for result）。使用归纳思维，先看只拥有1个鸡蛋的情况，思考什么是最坏情况。你可能说可以直接使用二分法，请注意，只有1个鸡蛋，必须保证找到临界层。所以，1个鸡蛋的情况下，最坏情况为 $r = 100$ （楼高）

大多数情况下，我们都低估了理解题意的重要性

这么思考还不够究竟，缺乏抽象思维

通过逻辑思考，可得 $r =100$ ，但有没有一个抽象的公式化结论？或者说，如何通过一个公式算出 $r$ ？接下来就来解决这个问题

假设临界层分别为 $x = 1,2,3 \dots 100$ ，因为你只有1个鸡蛋，不知道会在哪层碎，所以唯一策略是从1层开始一层一层试，对应的每个策略都有一个尝试步数（比如 $x = 95$ ，从1层开始尝试为95次），可得到临界层 $x$ 在所有可能取值下对应的 $r = 1,2,3 \dots 99,100$，最终选择最坏情况，即 $r = 100$

可抽象化得到待求的符号表达式
$$
r = \max_{1 \leqslant x \leqslant N}(\forall S_i(x)) \tag{1}
$$
公式的语言型描述是：对于每一个可能的临界层 $x$，得到使用可选择策略 $S_i()$ 需要的尝试步数。在每一轮 $x$ 的遍历中，取最大值（即最坏情况），为 $r$。无论临界层 $x$ 在哪一层，只有一个鸡蛋的情况下，总需考虑最坏情况

这道题，对1个鸡蛋问题的深刻理解异常重要。只有深刻理解基石逻辑才能更好的解决问题

2.2 两个鸡蛋

2.2.1 粗调和细调

依据粗条细调思维，我们有一次试错的机会。可以思考，假设第一个鸡蛋在 $k$ 层碎了，意味着什么？意味着，待求的临界层 $x$ 一定满足 $1 \leqslant x \lt k$ ，记为 $[1,k)$ ，就把待求量限制到了一个更小的范围内，可以提高找到目标值的效率

也就是说，使用第一个鸡蛋做粗调，碎了后，用第二个鸡蛋，参照1个鸡蛋的尝试策略细调。下一步，问题就变成了一个策略问题，即❓第一个鸡蛋应该在哪些层仍

在某层楼，丢一个鸡蛋，有两种结果：碎了和没碎。这句话是一个极为关键的信号，背后告诉我们这是一个树形结构问题

把数据结构与问题描述的勾连能力是衡量算法能力的重要指标

没有分叉，一路推理 ➜ 〔线性结构〕
看到决策结果有分叉 ➜ 〔树形结构〕
若在推理过程中，产生交汇 ➜ 〔图结构〕

下一节主要分析这条树形结构链

2.2.2 树形结构

假设第一个鸡蛋的楼层策略是 $k_1, k_2,\cdots,k_p$ ，其中 $p$ 是仍的总次数，楼高记为 $N$ 。比如如果你选择在 $20,40,60,80$ 层仍，那么 $p=4$ ，根据题意，有 $1 \lt k_1 \lt k_2 \lt \cdots \lt k_{p-1} \lt k_p \lt N$ 。画出树形示意图，如下图所示

图最上方的数轴就是一个横放的楼，$k_0 = 1$ 为第一层

〔解释这棵树〕在每一层扔下一个鸡蛋时，都有两种可能，碎了和没碎，分别对应了两个子树。一旦碎了，那么就使用1个鸡蛋的问题思路来解题，直到找到临界层。在 $k_1$层没碎，那么需在 $k_2$ 层继续尝试，直到最高层 $N$ 找到临界层（上图的标注不是树高，是灰色图例标识出部分的树高）

观察这颗树，怎样从树中得到对应问题的答案呢？

〔输入自变量〕 $k_1, k_2,\cdots,k_p$ 〔待求〕最小的尝试次数（即所有策略中最大值的最小值）等价于➜ 求一个策略组合 $k_1, k_2,\cdots,k_p$，使得树的高度最小

如果还是有些无法理解，此时，最好的方法就是看特例（举例子）

🌰 比如 $k_1 = 50$，意思是在50层扔下第一个鸡蛋

如果碎了，那么接下来的尝试方法就是从第1层开始一个一个往上尝试，直到49层，所以我们的答案 r = 50 （不记得如何计算这个值可以参考一个鸡蛋）
如果没碎，那么第一个鸡蛋继续在 k_2 = 75 层扔，假设还是没碎，继续从 k_3 = 90 层的地方扔下，此时碎了，那么第二课鸡蛋就需要从76层开始，一层一层往上尝试直到89层，需要 89-76+1=24 次，第一个鸡蛋已经扔了3次，最后得到没碎情况下的例子的答案 r=27 次

在上面的例子中，$k_1=50,k_2=75, k_3=90$ 就是一个可选策略

体会最坏情况下的最小值的意义非常重要，或者说，尝试的最大步数的最小值。如何判断对一道题目有没有完全吃透，看能否清晰的走完每一个例子，就能一窥一二

2.2.3 最优解的情况证明

⭐️ 接下里需要确定树的形状（同时也是确定策略的过程）。从直觉来看，如果树的形状倾向于满二叉树，那么树的高度最小。❓ 如何证明这个直觉的正确性呢？既然要计算树高，那么就把每一个叶子节点的树高一个一个列出来
$$ \left. \begin{array}{l} k_1 \\ k_2 -k_1 +1 \\ k_3-k_2 +2 \\ \cdots \\ k_p - k_{p-1} +{p-1} \\ N- k_p + p \\ \end{array} \right\} \sum = N + \frac{(1+p)p}{2} \tag{2} $$

经计算发现，所有树高的和是个定值。那么使用反证法，假设这棵树不是满树，因为高度和为定值，那么必定有一个高于平均值得树存在，记为 $T$ 。根据最高树的最小值的要求 $H_a ＜ H_T$ （$H_a$为满树的高度），答案是$H_a$ ，与不是满树的假设矛盾。所以，是满树。证毕

再参考树的示意图，所谓类似满二叉树是指每棵子树的树高相等，比如列出下面等式（每一行都是左右两颗子树相等，比如 $k_2$ 那棵树的树高即 $k_2 - k_1 -1 +2$），一层一层带入，都换成 $k_1$ 的表达式
$$ \begin{array} \\ k_1 &= k_2 - k_1 + 1 &\implies &k_2 = 2k_1 - 1 = k_1 + (k_1 - 1) \\ k_2 -k_1 +1 &= k_3-k_2 +2 &\implies &k_3 = 3k_1 -3 = k_1 + (k_1 -1) + (k_1 -2) \\ \cdots \\ k_{p-1} -k_{p-2} +p-2 &= k_{p}-k_{p-1}+ p - 1 &\implies &k_p = \underbrace{ k_1 + (k_1-1) + (k_1-2) + \cdots }_{p项} \end{array} \tag{3} $$

根据上述推倒发现规律：要满足条件每颗子树的树高相等，$k_p$ 的表达式是一个递减等差数列，最终必须在第 $N$ 层尝试（最后一次尝试走 $N - k_p$ 步，必须覆盖最后一层 $N$）。即在最小可分割的整数等差递减数列中，令 $k_p \sim N$ （趋近于），前半句加粗的话翻译成公式为

$$
k_1 + (k_1-1) + (k_1-2) + \cdots + 1 \sim N \implies \frac{k_1(k_1 + 1)}{2} = N \tag{4}
$$

解得 $k_1 \approx 13.65$ ，考虑到，所有尝试楼层都是整数，第一颗鸡蛋最后一次1颗鸡蛋的尝试区间需包含第 $N$ 层，所以 $k_1 = \lceil k_1\rceil = 14$ 。如果不明白为什么取上整数不取下整数，试试 $k_1 = 13$ 或 $k_1 = 14$ 对比一下答案，看看谁的尝试次数少即可

有了 $k_1$ ，带回（2）式，可以知道第一个鸡蛋的尝试楼层策略为 $14,27,39,50,60,69,77,84, 90,95,99$

使用这个策略，带回（1）式，假设临界层从1到N层，分别计算所需要的最多尝试次数，可得 $r = 14$

如果楼高 $N=200$，可计算得 $r = k_1 = 20$，策略为：第一次从20层开始尝试，没多一次尝试递减1

⭐️ 到此为止，2个鸡蛋问题解决：找到了一个明确的函数，利用抽象思维，写出它的表达式 $r = f(2, N)$，而这个 $f()$ 即求方程 $\frac{x(x+1)}{2} = N$ 解 $x$ 的上整数 $\lceil x \rceil$

3. 问题拓展

2个鸡蛋100层楼已经解决，深究下去，H层楼M个鸡蛋的问题呢？Leetcode有这道题：887. Super Egg Drop

刷题多的读者会快速反应出，这个问题是一道动态规划题，但在这里我还是想用一种推理的思维来尝试分析一遍，逻辑链上的关键锚点才是知识的精华

如果你通过观察题目，快速确定此题可用动态规划求解，这种能力是熟练能力，类似弹钢琴的熟能生巧，背书的死记硬背。与之相对，即分析能力。很有趣的是，这两种能力的分野十分明显，前者对应高效，后者对应求知

如果你需要快速通过面试，找工作或通过考试，那大量做题才是最短路径，可学习的目的不止是谋生，还有一种更高级的快乐来自于钻研本身，心理学管这种快乐为心流

回到问题，总结一下，通过上面的解答我们有了什么一些什么直观的结论

① 1个和2个鸡蛋的问题已经解决

② 理解了最大值的最小值在本题中的含义

③ 答案的值只和楼层高度有关，和最低楼层与最高楼层无关

以这三个结论为基石，想一想这道更一般化的问题怎么解决

3.1 符号化描述

首先，最容易想到的思考链条来自一个设问：❓我们能不能尝试把鸡蛋的数量减少？即不断的往2个鸡蛋的问题上靠拢？有一个很简单的办法，就是扔 ➜ 扔碎一个，鸡蛋数量就减少一个

照这个思路，进行一个抽象推演：假设在某一个时刻，我们拥有 $m$ 个鸡蛋，需要实验的层高为 $h$ （h for height），此刻在 $k \in [1, h]$ 层楼扔下一个鸡蛋

〔情况 1〕碎了

假设我们已经知道 $1$ 到 $k-1$ 层楼最优解的值，❓ 那怎么用一个函数来表示这个值呢？首先看我们需要的自变量有哪些

1）此时剩下的鸡蛋数，这个非常明显，符号化记为 $m$ 个鸡蛋
2）根据2个鸡蛋难题时的结论可知，第二个自变量是此时未知情况楼层的层高（未知情况只楼层范围内还从来没有用鸡蛋尝试过，无法缩小范围），符号化记为 $h$ 层（h for height）

⭐️ 用一个表达式 $r = f(h, m)$ 表示楼高为 $h$ 时，还剩下 $m$ 个鸡蛋时的最少尝试步数

因为在 $k$ 层碎了，所以不用考虑[k+1, N]层的情况（肯定都碎），并且因为此刻这一个鸡蛋碎了，剩下 $m-1$ 个鸡蛋，用式子 $f(k-1, m-1)$ 表示已经知道的 $1$ 到 $k-1$ 层楼最少尝试步数的值，总最小尝试次数为 $f(k-1, m-1)+1$

〔情况 2〕没碎

在 $k$ 层没碎，直接不用考虑[1, k]情况了（肯定都不碎），同理，计算出此时楼高 $h_{now} = h - (k+1) + 1 = h - k$，且因为此刻这个鸡蛋没碎，剩下 $m$ 个鸡蛋，即 $f(h-k, m)$ ，总最小尝试次数为 $f(h-k, m)+1$

3.2 构造逻辑链

此时，我们已经有了三个表达式

1️⃣ 楼高为 $h$ ，剩下 $m$ 个鸡蛋时的最少尝试步数：$f(h, m)$

2️⃣ 在第 $k$ 层扔下1个鸡蛋碎了后的最少尝试步数：$f(k-1, m-1)$

3️⃣ 在第 $k$ 层扔下1个鸡蛋没碎后的最少尝试步数：$f(h-k, m)$

那么，假设2️⃣3️⃣的表达式的答案已知，是否能用这二者推出1️⃣？如果上述逻辑链成立，就可以用归纳思维（数学归纳法）算出任意 $f(h, m)$ 。因为1️⃣只能从2️⃣3️⃣推出

〔推倒 $a$〕考虑到2️⃣3️⃣是一种策略选择后的可能性，根据上面的分析（最大值的最小值原理）两种策略中临界层 $x$ 可能在任何一层。遍历所有 $x$ 的情况时，最终尝试步数的结果是其中的最大值，所以选择2️⃣3️⃣中值更大的那个

〔推倒 $b$〕1️⃣需要仍一次鸡蛋，尝试步数 $+1$

〔推倒 $c$〕$k$ 是一个自变量，在这个情况下，可取到 $[1, h)$ 中的任意值，⭐️假设2️⃣3️⃣已知，只要在定义域内穷举出所有 $k$ 的可能值，并找出最大尝试步数中的最小值即可

接下来就可以把这个逻辑链的用抽象化的公式表达出来
$$
f(h, m) = \underbrace{\min_{1 \leqslant k \leqslant h} {\overbrace{\overbrace{\max [f(k-1, m-1), f(h-k,m)]}^{a}+1}^{b}}}_{c}\tag{5}
$$

有了具体的公式，为了锻炼工程思维，要时刻保持严谨，思考全集和完备性，再来看看边界条件和自变量定义域

3.2.1 自变量的定义域

依据题意楼高 $h \geqslant 1$ 且为整数，剩余鸡蛋数 $m \geqslant 1$ 且为整数

3.2.2 边界条件

$f(h, 1) = h$ ，当剩余鸡蛋数为1的时候，答案为现在的楼高

$f(0, m) = 0$ ，当楼高为0时，无法尝试，答案记为0 ，或者 $f(1,m) = 1$，表示楼高为1时，最小尝试次数为1

3.3 动态规划

现在反过头来再看，计算机学科中，有一部分专门研究这类问题的工具，即动态规划

上面的符号化描述被称为定义状态，构造逻辑链被称为构造状态转移方程，而背后的工程思维是拆分思维、抽象思维和归纳思维。再究竟一些，动态规划是一类特殊的图算法。

〔拆分思维〕拆分问题的能力。大问题化小问题，无后效性，当前状态与未来状态无关。
〔抽象思维〕使用状态来描述问题的能力，或说用抽象符号或状态机来描述问题的能力
〔归纳思维〕数学归纳法，逻辑推导能力。由 $\lt i$ 的所有状态推倒出 $i$ 时刻状态的能力

之所以要研究这类问题和计算机本身是一个巨大的状态机有关。动态规划提供了一套工具和思维框架去优化问题，找到最优解。思维框架和优化方法才是最厉害最有价值的，看到后面优化部分的详解你就能直观的体会到这点。

4. 实现优化和分析

这部分，通过一步一步剖析优化思路，和对应的代码实现（使用python，所有代码可在Leetcode题目中AC），希望能直观的说明一个问题，❓ 到底高级程序员和一般的码农程序员区分在哪里？

每个人都有自己擅长的领域，管理大师吉姆·柯林斯的第一本畅销书《基业长青》，书内研究了18家企业成功的秘密。

后来，他又出了一本书《从平庸到伟大》，对这个变化的界定是非常严格的。平庸意味着这家公司的业绩低于市场的平均水准，变得伟大意味着业绩保持在平均水准的3倍以上，并持续至少15年。他研究了1435家公司，只找到了11家

通过研究，他总结了这些企业的6个秘诀。其中一个就是著名的三环理论，如果把企业的三环理论推广到个人，就是问自己下面三个问题：我的擅长是什么？我的热爱是什么？我的机会是什么？

而选择三者交集作为一辈子的努力方向大概率就算是走对了路

作为程序员，可能只是你开始职业生涯的第一步，后面如何发展，需要对自己的追求和个人能力做一个更深入的挖掘，才能有个定论

下面即将剖析的优化过程完美的阐述了作为一个伟大的程序员需要什么样的基础能力（至少在算法优化这个小领域），这需要长时间的训练和极强的天赋。如果你感觉想出这些解答很吃力，相对应的，你又想这辈子有所作为，追逐伟大。那么应该尝试去找一条非程序员的路努力一生。毕竟，计算机思维，数据分析和机器学习未来会成为像数学一样的基础能力，无论在哪一行都对解决问题有极大的助益

4.1 基础版

根据思路直接写出的最直观代码。如果对递归理解的深，容易读懂。用我能想到最直白的语言来描述就是：假设子状态的结果已知，现在需要做些什么操作，就能得到此状态的答案，并且把这个答案返回给函数（借鉴知乎回答的答案，加上了lru_cache装饰器用于优化）

import functools
# python3的functools的一个自带函数, 可以对函数返回结果进行LRU cache, 下次以相同参数调用就不重复计算了
# maxsize=None 不限制大小, 其实就变成是全部都cache下来, 不考虑LRU了
@functools.lru_cache(maxsize=None) # 装饰器 
def f(h, m):
    if h == 0: return 0
    if m == 1: return h

    result = min ( [ max ( [ f( i - 1, m - 1 ), f( h - i, m ) ] ) for i in range( 1, h + 1 ) ] ) + 1
    return result

🔄〔优化〕Recursive（递归）的写法虽然清晰明了，但在工程上有调用函数的开销，系统栈深度限制等弊端，所以最好写成循环版本，否则在工作中可能返工

4.2 循环版本

def solve(h, m):
    if h < 1 and m < 1: return 0

    f = [ [ i for i in range(h+1) ] for j in range(m+1) ]

    for m_i in range( 2, m + 1 ):
        for h_j in range( 1, h + 1 ):
            for k in range( 1, h_j ):
                f[m_i][h_j]= min ( f[m_i][h_j], 1 + max( f[m_i -1][k - 1], f[m_i][h_j - k]) )
    
    return f[m][h]

🔄〔优化〕分析一下时间复杂度和空间复杂度，时间复杂度为 $O(mh^2)$ ，空间复杂度为 $O(hn)$ ，很明显，空间上可以优化到 $O(h)$，原因是状态转移方程只和 $m$ 与 $m-1$ 有关，使用两个数组滚动即可

4.3 空间优化版本

def solveSpace(h, m):
    if h < 1 and m < 1: return 0
    
    f_pre = f_cur = [i for i in range(h + 1)]

    for m_i in range( 2, m + 1 ):
        for h_j in range( 1, h + 1 ):
            for k in range ( 1, h_j ):
                f_cur[h_j] = min ( f_cur[h_j], 1 + max( f_pre[k - 1] , f_cur[h_j - k]) )
        f_pre = f_cur[:]
    
    return f_cur[h]

基本到这，对美国FAANG的入门级SDE，就十分优秀了。后面的所有的内容，属于高手的领域（博主完全不是高手，只是好奇，所以阅读了其他人的牛逼的解题报告，重新做了理解和整理）

对于这一套状态描述和状态转移方程，优化方向在时间复杂度上。思考，❓是否有一些数学定理可以提供答案取值的下界呢？（找边界是剪枝的有效方法）

🔄〔优化〕这里需要使用数据结构中折半查找判定树理论。假设我们对鸡蛋的数量不做限制，那么这棵树

就会变为一个满二叉树，而叶子节点数量有 $h+1$ 个（因为最大尝试步数能取到的总数就是 $h+1$ 种，需包含0次）树的高度至少为 $\lceil \log_2(h+1)\rceil$。假设鸡蛋 $m$ 的数量大于 $\lceil \log_2(h+1)\rceil $ ，那么上面的树变成满树，无论怎么尝试，答案（树高）都有一个下界（不可能大于这个值）

如果还不明白，即在 $m \geqslant \lceil \log_2(h+1)\rceil $ 时，这道题会变成二分查找（鸡蛋太多，随便扔，就当楼层是排序好的即可）最终答案直接取 $\lceil \log_2(h+1)\rceil$

🌰 如果还是不明白，上终极杀招，举例子。假设16层楼，但有4个鸡蛋。根本不用设计，二分查找即可，效率肯定最高。比如16层楼，只要鸡蛋数大于4，最大尝试次数就是4，可以直接算出答案

4.4 下界优化

def solveBoundary(h, m):
    if h < 1 and m < 1: return 0
    
    f_pre = f_cur = [i for i in range(h + 1)]
    
    for m_i in range( 2, m + 1 ):
        for h_j in range( 1, h + 1 ):
            t = math.ceil( math.log2( h_j + 1 ) )
            if m_i >= t:
                f_cur[h_j] = t
            else:
                for k in range ( 1, h_j ):
                    f_cur[h_j] = min ( f_cur[h_j], 1 + max( f_pre[k - 1] , f_cur[h_j - k]) )
        f_pre = f_cur[:]
    
    return f_cur[h]

这时候时间复杂度优化为 $O(mhlog_2(h))$。此时，如果列出所有状态转移的过程（行为鸡蛋数 $m$，从2开始；列为楼高 $h$ ，从1开始），如下图（红色框表示 $k$ 的移动，蓝色双向箭头表示 $\max$ 操作，然后还需要加1后和之前的 $f(m,h)$ 进行 $\min$ 操作。下图展示的是 $m_i=2,h_j=11,k=5$ 时的情况）（这幅图也能帮助理解下界优化，注意 $m_i=5$ 和 $m_i=4$ 在 $h < 20$ 的情况）

🔄 观察发现，有一个很重要的规律，即单调性，写成公式为 $f(m, h) \geqslant f(m, h-1)$ 当 $h \geqslant 1$ 。如果满足单调性，那么又可以在搜索时使用二分查找。先姑且不考虑如何证明单调性，工程上，在资源允许的情况下，先尝试，看看能不能得到正确结果（用正确算法和这个尝试算法进行验证）直到验证在很大的定义域内都正确，可大胆猜测这个猜测性质是对的（不严谨，但效率较高）

通过这一层优化，体现出了理论和工程的分野，即你猜想出了一个优化方法，当然可以先直接尝试，不管这个猜测的条件是不是正确。

反过头来仔细一寻摸，总是心里不踏实（可能出现特殊情况就让整个算法崩溃）此时，理论出山，用严谨的数学逻辑去证明这些结论，让算法具有完备性（本题单调性是正确的，证明过程参见参考文献）

另外，观察和总结答案的分布规律也是非常重要的思考手段，你会发现，这简单的一句话说开去，是一个新的学科，名叫统计学

4.5 单调性优化

def solveBinarySearch(h, m):
    if h < 1 and m < 1: return 0

    t = math.floor( math.log2( h ) ) + 1
    
    if m >= t: return t
    else:
        f_cur = f_pre = [i for i in range(h + 1)]

        for m_i in range(2, m + 1):
            f_cur[0] = 0
            for h_j in range(1, h + 1):
                f_cur[h_j] = 1000000
                start, stop = 1, h_j
                # 二分查找
                while start <= stop:
                    mid = (start + stop) // 2
                    if f_pre[mid - 1] > f_cur[h_j - mid]:
                        if f_pre[mid - 1] + 1 < f_cur[h_j]:
                            f_cur[h_j] = f_pre[mid - 1] + 1
                        stop = mid - 1
                    elif f_pre[mid - 1] < f_cur[ h_j - mid]:
                        if f_cur[h_j - mid] + 1 < f_cur[h_j]:
                            f_cur[h_j] = f_cur[h_j - mid] + 1
                        start = mid + 1
                    else:
                        f_cur[h_j] = f_cur[h_j - mid] + 1
                        break
            f_pre = f_cur[:]
        return f_cur[h]

🔄 结果的简单特性部分挖掘完了，继续观察上面的状态转移图，发现很多项是相等的，那么可不可以找到，在某种条件满足时，状态可以直接推出，而不用进行 $k$ 的遍历搜索？这个时候就需要从状态转移方程本身入手是挖掘其中的数学特性，这部分不是非常关键，较难，可直接跳过

$$ \begin{array}& f(h, m) = \min\limits_{1 \leqslant k \leqslant h} \{\max [f(k-1, m-1), f(h-k,m)]+1\} \\ f(h, m) \leqslant \max [f(k-1, m-1), f(h-k,m)]+1 \quad(1 \leqslant k \leqslant h) \\ 令\; k = 1 \implies f(h, m) \leqslant f(h - 1, m) + 1 \end{array} \tag{6} $$

又因为 $f$ 具有单调性，可得 $f(h - 1, m) \leqslant f(h, m) \leqslant f(h - 1, m) +1$ 其中 $h\geqslant 1$

上面的式子非常有意思，使用标准的逻辑推理来看

若某个决策 $k$ 可使得 $f(h - 1, m) = f(h, m)$ ，则一定 $f(h, m) = f(h-1, m)$
若所有决策 $k$ 都不能使 $f(h - 1, m) = f(h, m)$ ，则一定 $f(h, m) = f(h - 1, m) + 1$

那么，是否可以构造这样一个决策，使得状态转移直接计算呢？具体过程略过，有兴趣的读者详见参考文献

假设这个决策的楼高 $h = p$ ，推倒出当 $f(m, p)<f（m-1， h-p-1)$ 时，无论任何决策都不能使 $f(m, h) = f(m, h-1)$，所以，此时 $f(m, h) = f(m, h-1) + 1$

也就是说，根据 $f(m, p)$ 和 $f(m-1,h-p-1)$ 的大小关系就可以直接确定 $f(m, h)$

4.6 状态转移方程优化

def solveTransferFunction(h, m):
    if h < 1 and m < 1: return 0

    t = math.floor( math.log2( h ) ) + 1  
    if m >= t: return t
    else:
        f_cur = [i for i in range(h + 1)]
        f_pre = [i for i in range(h + 1)]

        for m_i in range(2, m + 1):
            p = f_cur[0], f_cur[1] = 0, 1
            for j in range(2, h + 1):
                if f_cur[p] >= f_pre[j - p - 1]:
                    f_cur[j] = f_cur[j - 1]
                else:
                    f_cur[j] = f_cur[j - 1] + 1
                    p = j - 1
            f_pre = f_cur[:]
        
        return f_cur[h]

此时，状态转移过程时间复杂度变成 $O(1)$，整体时间复杂度随之变成 $O(m\log_2{h})$

在这种依照题意直接定义状态并找到状态转移方程的方法已经优化到极致了。那么，❓ 如果从不同的角度定义问题呢？

4.7 不同角度看问题

4.7.1 状态定义

改变对问题的状态描述方法，用 $h(i,j)$ [h for height]表示用 $j$ 个鸡蛋尝试 $i$ 次在最坏情况下能找到的最小尝试次数的楼高。

4.7.2 边界条件

当尝试次数 $i=1$ 时，$h(1,j)=1\quad(j \geqslant 1)$

当使用 $j = 1$ 个鸡蛋时，尝试 $i$ 次可以尝试 $i$ 层楼，即 $h(i,1)=i$

4.7.3 状态转移方程

核心思路：每一次 $h()$ 所能尝试的楼高必须要尽可能的大，这样才能做到尝试次数最小

在某层扔下一个鸡蛋

〔碎了〕那么在后面的 $i-1$ 次里，需用 $j-1$ 个鸡蛋在下面的楼层中确定楼高。为了使 $h(i,j)$ 达到最大，希望下面的楼层数（楼高）最大，根据状态定义，记为 $h(i-1, j-1)$
〔没碎〕那么在后面的 $i-1$ 次里，需用 $j$ 个鸡蛋在上面的楼层中确定楼高。同理，需要楼层数达到最大，记为 $h(i-1,j)$

综上，状态转移方程写为 $h(i,j) = h(i-1, j-1)+h(i-1,j) + 1$

而最终结果可以写为，找到一个 $x$ ，使得 $x$ 满足 $h(x-1, M) < H$ 且 $h(x, M) \geqslant H$ （$M$ 为鸡蛋总数，$H$ 为楼层总高度），其实也就是用公式描述的临界层的具体含义

4.7.4 代码实现

def g(h, m):
    if h < 1 and m < 1: return 0

    t = math.floor( math.log2( h ) ) + 1 
    if m >= t: return t
    else:
        g_cur = g_pre = [ 1 for i in range(m + 1) ]
        g_cur[0] = g_pre[0] = 0

        if g_cur[m] >= h: return 1
        elif h == 1: return h
        else:
            for i in range(2, h + 1):
                for j in range( m, 1, -1):
                    g_cur[j] = g_pre[j - 1] + g_pre[j] + 1
                    if g_pre[j] < h and g_cur[j] >= h:
                        return i
                g_cur[1] = i
                if m == 1 and g_cur[1] >= h:
                    return i
                print( g_cur, end="\n")
                g_pre = g_cur[:]

4.7.5 继续优化

这又是一个全新的状态定义和状态转移方程，同理，可尝试输出整个转移矩阵的具体值，先观察一下总没有错，如下图所示

从形式上来说，不需要滚动数组，在转移过程中，使用一个 $g$ 函数即可。在最后输出的时候，只需要判断g[m]的情况输出 $i$

def gOptimization(h, m):
    if h < 1 and m < 1: return 0

    t = math.floor( math.log2( h ) ) + 1
    
    if m >= t: return t
    else:
        g = [ 1 for i in range(m + 1) ]
        g[0] = 0

        if g[m] >= h: return 1
        elif h == 1: return h
        else:
            for i in range(2, h + 1):
                for j in range( m, 1, -1):
                    g[j] = g[j - 1] + g[j] + 1
                    if j == m and g[j] >= h:
                        return i
                g[1] = i
                if m == 1 and g[1] >= h:
                    return i

要分析时间复杂度，挺难的。通过证明可以有一个结论（具体证明详见参考文献）$xM \leqslant H$ ，再通过一系列骚操作，可以证明时间复杂度为 $O(\sqrt{h})$，空间复杂度 $O(m)$

至此，Leetcode上这道题目的执行时间打败了85.7%的答案（虽然Leetcode时间并不靠谱），做这道题的人不多，前面只有一个答案，思路类似，代码写的更漂亮

5. 工程思维总结和感悟

5.1 工程思维

⭐️ 这一部分是【直观算法】系列的最终目的。求同遵异，寻找每一道算法题背后的工程思维，提升自己真正解决工程问题的能力。博主对自己的定位是【机器学习+区块链产品经理】，但同时对技术也有好奇心，喜欢钻研，才开坑写【直观算法】系列

5.1.1 抽象思维

把语言描述转化为符号描述的能力，符号是信息和逻辑的纽带

5.1.2 等价思维

沟通的效率和信息的冗余度成正比，所以一个人能否把同一个概念，从不同的角度，用不同的案例类比，抑或各类精彩直观的比喻表达出来，这个能力很重要，它可以让人们更加准确快速的理解你想表达的意思

⭐️ 学习的真正本质：是在一个领域内不断的去建立这种沟通共识的框架。举个例子，学过线性代数的人，只要提到矩阵，就能想到变换。这就是都学过线性代数的人交流密码，如矩阵的逆 = 一个具体的反向变换。没学过这门课的人是无法和学过的人进行沟通的。这也从很大程度加强了人们沟通的效率，所以，学习带来的终极成效之一其实是降低了人类社会的沟通时间，提高了效率

再举个例子：机器学习中，提到正则化，必须建立一套与之相关的知识架构，包括，过拟合，最优化函数曲面空间理解，范数等，成树状结构继续推而广之，这每一个名词，背后也对应了一个更加直观，更加易懂的描述方式。但是我们需要知道，如果我为了表达正则化，为了让你明白我的意思，我需要用一大堆描述性语言，那我们两人的沟通效率就十分低下了

这也就是知识体系，一门学科，一门专业的最终含义，学习是为了构建这门学科的通识沟通框架，降低同行之间的沟通成本。当然，这有一个必要前提，把学习的目的理解降低沟通成本必须是你做的工作是规模化的，涉及协作

如果你是爱因斯坦，是能开拓学科新领域的0级工程师（来自于吴军老师谷歌方法论），独自想象钻研。那么，学习的本质可能在于给你更多的角度（认知能力），更多的工具（锤子锯子）去更好的探索这个世界的本质和规则，在这样的条件下，关于学习本质的描述就需要调整了

5.1.3 反推思维

从结论出发反推逻辑链

5.1.4 归纳思维

数学归纳法，使用已有的条件信息，归纳推出待求的内容

5.1.5 粗条细调思维

对于这道题，首先考察的是程序员的粗条细调思维。工程中经常会有对测量精度的要求，那么是如何做的？比如常见的千分尺，首先是一个横向的卡尺来接近目标值，然后用一个滚轮形的第二级继续细调。同样，显微镜也有对应的调整方法。都可以总结为粗条细调思维

首先大步接近最优解，再调整迭代速度，更加细微的接近最优解。机器学习中的，Adam优化器也是用类似的思维来设计的

5.1.6 拆分思维

问题是否能拆分几个黑盒，只给输入输出，里面的逻辑链做到精简，或者有已经可用的轮子和算法直接应用的能力。

能看到这的读者我衷心感谢您的求知欲和耐心（我写的比较啰嗦，为了权衡不同背景的读者），下面的一部分个人认为才是最重要的

5.2 工程应用

到了这一步，基本压榨了本题所有的潜力。但是，下一个值得思考的问题就是，这道题目对应的算法在实际工程和解决问题的具体情况中有没有什么应用呢？答案是肯定的

🌰 如果要找学科分类，鸡蛋难题属于运筹学问题，典型应用是破坏性试验，如测试汽车、飞机、火箭等的若干极限性能。举个例子，汽车保全乘客安全的最高碰撞末速，那么为了保证能找这个值，一定会用类似的思路来解决问题。

你可能也已经发现，具体问题一定还是具体分析，但这道题目对应的工程思维更像是工具箱里面的一种更强大的工具。

记得罗辑思维中提过一个问题：为什么物理学领域老一辈的物理学家现在拿奖的人越来越少？其中一个重要的原因是他们熟悉的物理学工具没有新生一辈的能力强大的。不同于数学这类逻辑学科，物理学是可验证学科，实验，测量工具和理论工具等都必不可少

博主笃定，算法80%是要为解决问题服务的，勾起人们学习的最佳动力就是举实际生活中遇到的难题是如何用这个算法解决。从这个侧面，有关字符串的算法就非常能勾起学习的兴趣，正是因为涉及到字符串处理的情景太多。

关于鸡蛋难题，总的看下来，完美的诠释了直观 ➜ 抽象的思维链条。所有高效的，精简的算法，就是要找到事物或者逻辑发生的本质规律，如果不谈完备性的证明，用图表和直观的性质来描述，这道题目的优化思路并不难（相对的，完备性时间复杂度的证明才是难点）

关于剩下的20%，此时又想起黎曼猜想，所有非平凡零点的有关性质。趋向于无穷、所有、任意这些定义方式是人类为了寻找边界而设计的工具。趋向于无穷大，趋向于无穷小都还有很多问题没有解决。罗胖说，创业者是在开垦商业的边疆，那么理论科学家就是拿着这些强大的工具开拓逻辑和思维的边疆，在一片荒芜上安营扎寨，仰望星空。这可能就是人类群体中最有魅力的事业吧？

【参考文献】

非常感谢计算机信息学奥赛国家队朱前辈的论文，对这道题目做了完美的剖析，也勾起了我的好奇心，一探究竟，才有了这篇万字长文

吴育昕的回答 - 知乎

参考文献：朱晨光：《优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化》

【直观算法】Egg Puzzle 鸡蛋难题